package com.sunqianhu.algorithm.sort.swap.quick_sort;

public class QuickSort {
    /**
     * 快速排序主方法
     * @param arr   要排序的数组
     * @param low   排序区间的起始索引
     * @param high  排序区间的结束索引
     */
    public static void sort(int[] arr, int low, int high) {
        //如果开始索引小于结束索引，则继续递归
        if (low < high) {
            //先对数组进行分区，找到基准值的正确位置
            int pivotIndex = partition(arr, low, high);
            //对左边子数组递归排序（不包含基准）
            sort(arr, low, pivotIndex - 1);
            //对右边子数组递归排序（不包含基准）
            sort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        //基准值
        int pivot = arr[low];
        //“挖掉”第一个元素，留下一个“空位”
        while (low < high) {
            //从右往左找比 pivot 小的元素
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            //立即放到“空位”上（也就是pivot原来的位置）
            swap(arr, low, high);
            //从左往右找比 pivot 大的元素
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            swap(arr, low, high);
        }
        //最后把 pivot 放回“空位”
        arr[low] = pivot;

        // 返回基准位置
        return low;
    }

    /**
     * 分区操作：将比基准小的数放左边，大的放右边
     * 最后将基准放到正确的位置，并返回该位置
     * @param arr   要排序的数组
     * @param low   当前排序区间的起始索引
     * @param high  当前排序区间的结束索引
     * @return      基准元素最终所在的索引位置
     */
    private static int partition2(int[] arr, int low, int high) {
        int pivot = arr[low]; //选择第一个元素作为基准
        int i = low; //i从第2个元素开始比较
        int j = high + 1; //j从最后一个元素开始比较
        while (true) {
            //从第二个元素开始比较，找到比基准大的元素的索引
            while (arr[++i] < pivot) {
                if (i >= high) {
                    break;
                }
            }
            //从最后一个元素开始比较，找到比基准小的元素的索引
            while (arr[--j] > pivot) {
                if (j <= low) {
                    break;
                }
            }
            //如果左边索引等于右边索引，则说明左右两边已全部扫描完毕，退出循环
            if(i >= j){
                break;
            }
            //将左边比基准大的元素和右边比基准小的元素交换位置
            swap(arr, i, j);
        }
        //将基准放到中间位置
        swap(arr, low, j);
        return j;//返回基准的位置
    }

    /**
     * 辅助方法：交换数组中两个位置的元素
     * @param arr 数组
     * @param i   第一个位置
     * @param j   第二个位置
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 打印数组的方法
     * @param arr 要打印的数组
     */
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    /**
     * 主函数：程序入口
     * @param args 命令行参数（未使用）
     */
    public static void main(String[] args) {
        // 定义一个待排序的数组
        int[] arr = {57,68,59,52,72,28,96,33,24,19};

        // 打印原始数组
        System.out.println("原数组为：");
        printArray(arr);

        // 调用快速排序方法进行排序
        sort(arr, 0, arr.length - 1);

        // 打印排序后的数组
        System.out.println("排序后数组为：");
        printArray(arr);
    }
}
